
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1729. -- [Usaco2005 dec]Cow Patterns -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1729: [Usaco2005 dec]Cow Patterns</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>53&nbsp;&nbsp;<span class=green>Solved: </span>27<br>[<a href='submitpage.php?id=1729'>Submit</a>][<a href='problemstatus.php?id=1729'>Status</a>][<a href='bbs.php?id=1729'>Discuss</a>]</center><h2>Description</h2><div class=content>
A particular subgroup of K (1 <= K <= 25,000) of Farmer John's cows
likes to make trouble. When placed in a line, these troublemakers
stand together in a particular order. In order to locate these
troublemakers, FJ has lined up his N (1 <= N <= 100,000) cows. The
cows will file past FJ into the barn, staying in order. FJ needs
your help to locate suspicious blocks of K cows within this line
that might potentially be the troublemaking cows.

FJ distinguishes his cows by the number of spots 1..S on each cow's
coat (1 <= S <= 25). While not a perfect method, it serves his
purposes. FJ does not remember the exact number of spots on each
cow in the subgroup of troublemakers. He can, however, remember
which cows in the group have the same number of spots, and which
of any pair of cows has more spots (if the spot counts differ). He
describes such a pattern with a sequence of K ranks in the range
1..S.  For example, consider this sequence:

      1 4 4 3 2 1

In this example, FJ is seeking a consecutive sequence of 6 cows
from among his N cows in a line. Cows #1 and #6 in this sequence
have the same number of spots (although this number is not necessarily
1) and they have the smallest number of spots of cows #1..#6 (since
they are labeled as '1').  Cow #5 has the second-smallest number
of spots, different from all the other cows #1..#6.  Cows #2 and
#3 have the same number of spots, and this number is the largest
of all cows #1..#6.

If the true count of spots for some sequence of cows is:

 5 6 2 10 10 7 3 2 9

then only the subsequence 2 10 10 7 3 2 matches FJ's pattern above.

Please help FJ locate all the length-K subsequences in his line of
cows that match his specified pattern.
</div><h2>Input</h2><div class=content>* Line 1: Three space-separated integers: N, K, and S

* Lines 2..N+1: Line i+1 describes the number of spots on cow i.

* Lines N+2..N+K+1: Line i+N+1 describes pattern-rank slot i.

</div><h2>Output</h2><div class=content>* Line 1: The number of indices, B, at which the pattern matches

* Lines 2..B+1: An index (in the range 1..N) of the starting location
        where the pattern matches.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
9 6 10<br />
5<br />
6<br />
2<br />
10<br />
10<br />
7<br />
3<br />
2<br />
9<br />
1<br />
4<br />
4<br />
3<br />
2<br />
1<br />
<br />
INPUT DETAILS:<br />
<br />
The sample input corresponds to the example given in the problem statement.<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
1<br />
3<br />
<br />
OUTPUT DETAILS:<br />
<br />
There is only one match, at position 3 within FJ's sequence of N cows.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1729'>Submit</a>][<a href='problemstatus.php?id=1729'>Status</a>][<a href='bbs.php?id=1729'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
